package Sort.SortTest;


/**
 * @author shy_black
 * @date 2019/8/2 14:42
 * @Description:
 *
 * 复习：堆排序--
 *  堆--满二叉树-->除底层外，每一层都是满的，，并且所有结点都保持向左对齐
 *  这时我们找最后一个非叶子节点就转换为求 （arr.length-1） / 2  ---  元素下标以0 开始
 *  要进行堆排序，先构造一个初始的二叉堆，假设现在需求为升序，先构造一个大顶堆
 *      从最后一个非叶子节点（i）开始，进行建堆--
 * 建堆步骤：
 * 1：如父节点小于叶子节点中较大的一个，交换，否则当前节点建堆成功，i--,继续循环
 * 2：如步骤1中交换，则判断交换后子节点所在的树是否满足堆的性质，重复步骤1
 *      注意：步骤1满足时，进行操作i= k,使当前节点变为子节点
 */
public class 堆排序 {
    public static void heapSort(int[] arr) {

        for(int i = (arr.length-1) / 2 ;i >= 0; i --) {
            sort(arr,i,arr.length);
        }

        for(int i = arr.length-1;i >= 0;i--) {
            swap(arr,0,i);

            sort(arr,0,i);
        }

    }
    public static void sort(int[] arr ,int i ,int length) {
        int tmp = arr[i];

        for (int k = 2 * i + 1;k < length ;k = 2 * k + 1) {

            if(k + 1 < length && arr[k] < arr[k+1]) {
                k++;
            }

            if(arr[k] > tmp) {
                swap(arr,i,k);
                i = k;
            }else {
                break;
            }
        }

    }


    private static void swap(int[] arr,int i,int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    public static void main(String[] args) {
        int[] arr = new int[]{4, 3, 6, 2, 7, 3, 6, 3, 89, 5, 4, 5, 2, 8, 0};
        heapSort(arr);
        for(int i : arr) {
            System.out.print(i + "-");
        }
    }
}